package basic_datastructure.linear;

/**
 * 队列的入队和出队操作实现
 * 时间复杂度：入队和出队都为O(1)
 */

public class MyQueue {
    private int[] array;
    private int front;  //定义队头
    private int rear;   //定义队尾

    MyQueue(int capacity){
        this.array = new int[capacity];
    }

    /**
     * 入队操作
     * 越界判断条件：队列已满(rear+1)%array.lenght == front
     *
     * @param element 入队的元素
     */
    public void enQueue(int element) throws Exception {
        //越界判断
        if (((rear + 1) % array.length) == front) {
            throw new Exception("队列已满！");
        }
        //入队
        array[rear] = element;
        //队尾移动
        rear = (rear + 1) % array.length;
    }

    /**
     * 出队
     * 越界判断：front == rear ： 队列为空
     *
     * @return 返回出队元素
     * @throws Exception
     */
    public int deQueue() throws Exception {
        if (front == rear) {
            throw new Exception("队列为空");
        }
        //出队
        int deQueueElement = array[front];
        //移动队头
        front = (front + 1) % array.length;
        return deQueueElement;
    }

    /**
     * 输出队列
     */
    public void printQueue() {
        for (int i = front; i != rear; i = (i + 1) % array.length) {
            System.out.print(array[i] + " ");
        }
    }

    public static void main(String[] args) throws Exception {
        MyQueue myQueue = new MyQueue(6);
        myQueue.enQueue(3);
        myQueue.enQueue(6);
        myQueue.enQueue(1);
        myQueue.enQueue(8);
        myQueue.enQueue(7);
        System.out.print("队列中元素：");
        myQueue.printQueue();
        System.out.println();

        myQueue.deQueue();
        myQueue.deQueue();
        myQueue.deQueue();
        System.out.print("队列中元素：");
        myQueue.printQueue();
        System.out.println();

        myQueue.enQueue(2);
        myQueue.enQueue(4);
        myQueue.enQueue(9);
        System.out.print("队列中元素：");
        myQueue.printQueue();
        System.out.println();
    }
}
